//
//  Problem638.swift
//  TestProject
//
//  Created by 武侠 on 2021/3/8.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 638. 大礼包 【动态规划】【数字】【相减】
 在LeetCode商店中， 有许多在售的物品。
 然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。
 现给定每个物品的价格，每个大礼包包含物品的清单，以及待购物品清单。请输出确切完成待购清单的最低花费。
 每个大礼包的由一个数组中的一组数据描述，最后一个数字代表大礼包的价格，其他数字分别表示内含的其他种类物品的数量。
 任意大礼包可无限次购买。

 示例 1:

 输入: [2,5], [[3,0,5],[1,2,10]], [3,2]
     输出: 14
     解释:
     有A和B两种物品，价格分别为¥2和¥5。
     大礼包1，你可以以¥5的价格购买3A和0B。
     大礼包2， 你可以以¥10的价格购买1A和2B。
     你需要购买3个A和2个B， 所以你付了¥10购买了1A和2B（大礼包2），以及¥4购买2A。
 示例 2:
     输入: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]
     输出: 11
     解释:
     A，B，C的价格分别为¥2，¥3，¥4.
     你可以用¥4购买1A和1B，也可以用¥9购买2A，2B和1C。
     你需要买1A，2B和1C，所以你付了¥4买了1A和1B（大礼包1），以及¥3购买1B， ¥4购买1C。
     你不可以购买超出待购清单的物品，尽管购买大礼包2更加便宜。
 说明:
     最多6种物品， 100种大礼包。
     每种物品，你最多只需要购买6个。
     你不可以购买超出待购清单的物品，即使更便宜。
 */
@objcMembers class Problem638: NSObject {
    func solution() {
        print(shoppingOffers([2,5], [[3,0,5],[1,2,10]], [3,2]))
        print(shoppingOffers([2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]))
    }
    
    /*
     动态规划
     1: 创建一个字典dp[key:int] key = [6, 2, 1] = "6,2,1,"
     2: dp[key]: 购买key，需要的最便宜价格
     3: dp[key] = min()
        1: 我全部单独购买  dp[key] = price * needs
        2: 我选择礼包（包括：全部是礼包、礼包+单独）
        for (i in 0...special.count) {
            // 判读第一个大礼包是否购买
            if (可以购买了第一个大礼包) {
                dp[key] = special.last + dp[key - special] // 第一个大礼包的价格 + 剩下物品需求的最低价格
            } else {    // 说明购买第一个不满足条件
                continue
            }
        }
     */
    func shoppingOffers(_ price: [Int], _ special: [[Int]], _ needs: [Int]) -> Int {
        var dp:[String:Int] = [:]
        
        let value = shoppingOffersDP(price, special, needs, &dp)
        print(dp)
        return value
    }
    
    func shoppingOffersDP(_ price: [Int], _ special: [[Int]], _ needs: [Int], _ dp: inout [String:Int]) -> Int {
        let key = getArrayKey(needs)
        print("key = \(key)")
        if dp[key] != nil {
            return dp[key]!
        }
        
        // 1: 假如全部单独购买
        var value = 0
        for i in 0..<price.count {
            value += price[i] * needs[i]
        }
        dp[key] = value
        
        // 2: 我选择礼包（包括：全部是礼包、礼包+单独）
        // 挨个购买每一个礼包，看看哪个花费最小
        for i in 0..<special.count {
            var tempNeeds = needs       // 每次复制一份，为了尝试的购买每一份礼包
            
            // 校验该礼包是否可以购买
            var isNeed = true
            for j in 0..<special[i].count-1 {
                if tempNeeds[j] - special[i][j] < 0  {  // 说明：礼包里面该物品 大于 需要购买的数量，不符合
                    isNeed = false
                    break
                }
                tempNeeds[j] -= special[i][j] // 需要购买的数量 - 礼包中该物品的数量
            }
            
            if isNeed == true {     // 说明礼包符合条件
                dp[key] = min(dp[key]!, special[i].last! + shoppingOffersDP(price, special, tempNeeds, &dp))
            }
        }
        return dp[key]!
    }
    
    func getArrayKey(_ array:[Int]) -> String {
        var key = ""
        for i in 0..<array.count {
            key += String(array[i]) + ","
        }
        return key
    }
}
